package algorithm.middle;


/**
 * @author 江岸
 * @version V1.0
 * @ClassName: NumMatrix304
 * @description: 给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。
 *
 * Range Sum Query 2D
 * 上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。
 *
 *
 *
 * 示例：
 *
 * 给定 matrix = [
 *   [3, 0, 1, 4, 2],
 *   [5, 6, 3, 2, 1],
 *   [1, 2, 0, 1, 5],
 *   [4, 1, 0, 1, 7],
 *   [1, 0, 3, 0, 5]
 * ]
 *
 * sumRegion(2, 1, 4, 3) -> 8
 * sumRegion(1, 1, 2, 2) -> 11
 * sumRegion(1, 2, 2, 4) -> 12
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/range-sum-query-2d-immutable
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/3/29:42
 * @since V1.0
 */
public class NumMatrix304 {
    int[][] arr;

    //前缀和 二维数组
    public NumMatrix304(int[][] matrix) {
        if (matrix.length==0){
            return;
        }
        arr = new int[matrix.length + 1][matrix[0].length + 1];
        for (int i=1;i<arr.length;i++){
            for (int j=1;j<arr[0].length;j++){
                arr[i][j] = arr[i][j-1] + arr[i-1][j] +  matrix[i-1][j-1] - arr[i-1][j-1];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return  arr[row2+1][col2+1] + arr[row1][col1] - arr[row1][col2+1] - arr[row2+1][col1];
    }
}
